/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& prev,int begin,int end) {
        if(begin>end)
            return nullptr;
        TreeNode* newnode= new TreeNode(preorder[prev]);
        int root=begin;
        while(root<=end)
        {
            if(inorder[root]!=preorder[prev])
                root++;
            else
                break;
        }
        prev++;//prev是前序的遍历
        //[begin,root-1] [root] [root+1,end].  分割区间
        newnode->left=_buildTree(preorder,inorder,prev,begin,root-1);
        newnode->right=_buildTree(preorder,inorder,prev,root+1,end);
        return newnode;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i=0;//prev跟着递归增加，得是变量
        return _buildTree(preorder,inorder,i,0,preorder.size()-1);
    }
};